package algorithm.niuke;

import java.util.Stack;

public class 特殊的二进制序列 {
    boolean log = true;

    public String makeLargestSpecial(String S) {
        // 连续的特殊串，组成的大串也是特殊串
        int len = S.length();
        char[] chs = S.toCharArray();
        String continueStr = "";
        int preE = 0;
        String pre = "";
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (chs[i] == '0') {
                String top = stack.pop();
                if (top.length() > 1) {
                    if (log) {
                        System.out.println(top);
                    }
                    continueStr = "1" + top + "0";
                    stack.pop();
                } else {
                    continueStr = "10";
                }
                top = stack.isEmpty() ? null : stack.peek();
                while (top != null && top.length() > 1) {
                    top = stack.pop();
                    continueStr = max(top, continueStr);
                    top = stack.isEmpty() ? null : stack.peek();
                }
                stack.push(continueStr);
                continueStr = "";
            } else {
                if (continueStr.length() <= 0) {
                    continueStr = "1";
                }
                stack.push(continueStr);
                continueStr = "";
            }
        }
        return stack.pop();
    }

    String max(String str1, String str2) {
        String str3 = str1 + str2;
        String str4 = str2 + str1;
        if (str3.compareTo(str4) > 0) {
            return str3;
        } else {
            return str4;
        }
    }

    public static void main(String[] args) {
        String str = "1011100100101100";
        特殊的二进制序列 run = new 特殊的二进制序列();
        run.makeLargestSpecial(str);
        //a b c d
    }
}
